package cn.lucky.datastructure.linked;

/**
 * @author lingpeng.jiang
 * @create 2021-02-01-21:00 单向链表的实现
 */
public class SignLinkedListTest {

    public static void main(String[] args) {
        SignLinkedList lickedList = new SignLinkedList();
        lickedList.addHead(1);
        lickedList.addHead(2);
        lickedList.addHead(3);
        lickedList.display();
        lickedList.delHead();
        lickedList.display();
        System.out.println(lickedList.find(2));
    }
}

/**
 * 定一个单向链表
 */
class SignLinkedList{

    private int size;
    private Node head;

    public SignLinkedList(){
        this.size = 0;
        this.head = null;
    }

    /**
     * 内部节点对象
     */
    static class Node{
        private Object data;
        private Node next;

        public Node(Object data){
            this.data = data;
            this.next = null;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "data=" + data +
                    ", next=" + next +
                    '}';
        }
    }


    /**
     * 在链表头部添加元素
     * @param data
     * @return
     */
    public Object addHead(Object data){
        Node newNode = new Node(data);
        if (size == 0){
            head = newNode;
        }else{
            newNode.next = head;
            head = newNode;
        }
        size++;
        return data;
    }

    /**
     * 删除头结点
     * @return
     */
    public Object delHead(){
        Object data = head.data;
        head = head.next;
        size--;
        return data;
    }

    /**
     * 查询链表中的元素
     * @param data
     * @return
     */
    public Node find(Object data){
        if (size == 0){
            throw new RuntimeException("this linked size is null");
        }
        Node current = head;
        int tempSize = size;
        while (tempSize > 0){
            if (data.equals(current.data)){
                return current;
            }else{
                current = current.next;
            }
            tempSize--;
        }
        return null;
    }


    /**
     * 判断链表是否为空链表
     * @return
     */
    public boolean isEmpty(){
        return size == 0;
    }

    /**
     * 删除指定节点
     * @param data
     */
    public boolean delNode(Object data){
        if (isEmpty()){
            return false;
        }
        //当前要删除节点，默认为head
        Node current = head;
        //当前要删除的节点的上一节点，默认head
        Node previous = head;
        //如果没有找到指定的节点则循环继续
        while (!data.equals(current.data)){
            //最后一个节点还不是要找的，则直接返回false
            if (current.next == null){
                return false;
            }else{
                // 节点后移
                previous = current;
                current = current.next;
            }
        }
        //如果是头结点，则将下一节点变为头结点
        if (current.equals(head)){
            head = current.next;
        }else{
            //不是头结点，则将当前节点的下一节点，连接到当前节点的上一节点的下一节点上
            previous.next = current.next;
        }
        size--;
        return true;
    }


    /**
     * 遍历显示所有的节点的信息
     */
    public void display(){
        if (isEmpty()){
            System.out.println("[]");
        }else{
            Node current = head;
            int tempSize = size;
            if (tempSize == 1){
                System.out.print("[ " + head.data + " ]");
            }
            while (tempSize > 0){
                if (current == head){
                    System.out.print("[ " + current.data + "->");
                }else if (current.next == null){
                    System.out.print( current.data + " ]");
                }else{
                    System.out.print(current.data + "->");
                }
                tempSize--;
                current = current.next;
            }
            System.out.println();
        }
    }

}
